In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length n and given minimum distance d.
Statement of the bound[edit]
A code is considered "binary" if the codewords use symbols from the binary alphabet
. In particular, if all codewords have a fixed length n,
then the binary code has length n. Equivalently, in this case the codewords can be considered elements of vector space
over the finite field
. Let
be the minimum distance of
, i.e.
![{\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e73f891020bc785b36d30140365ccd451b750513)
where
is the Hamming distance between
and
. The expression
represents the maximum number of possible codewords in a binary code of length
and minimum distance
. The Plotkin bound places a limit on this expression.
Theorem (Plotkin bound):
i) If
is even and
, then
![{\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e58535f3ab60d3fa670debd5312e33e0068e7b)
ii) If
is odd and
, then
![{\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d+1}{2d+1-n}}\right\rfloor .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a2c138b829d33fa87e2c1c7e78b313db0641bb9)
iii) If
is even, then
![{\displaystyle A_{2}(2d,d)\leq 4d.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8bc8d4b56bc3361f340c4705ac06c0fa5cf27e80)
iv) If
is odd, then
![{\displaystyle A_{2}(2d+1,d)\leq 4d+4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ae6593f7fbbae83b1e128b7e9e9624e7a987ed8)
where
denotes the floor function.
Proof of case i[edit]
Let
be the Hamming distance of
and
, and
be the number of elements in
(thus,
is equal to
). The bound is proved by bounding the quantity
in two different ways.
On the one hand, there are
choices for
and for each such choice, there are
choices for
. Since by definition
for all
and
(
), it follows that
![{\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)\geq M(M-1)d.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c046c14f140f61e15e9ca7ba560fe088992cdb52)
On the other hand, let
be an
matrix whose rows are the elements of
. Let
be the number of zeros contained in the
'th column of
. This means that the
'th column contains
ones. Each choice of a zero and a one in the same column contributes exactly
(because
) to the sum
and therefore
![{\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)=\sum _{i=1}^{n}2s_{i}(M-s_{i}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55deb3175f041370c13b010f63a8c479fd487d29)
The quantity on the right is maximized if and only if
holds for all
(at this point of the proof we ignore the fact, that the
are integers), then
![{\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)\leq {\frac {1}{2}}nM^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92ad00664e5ad8168c09385e5eafe4773eefbb89)
Combining the upper and lower bounds for
that we have just derived,
![{\displaystyle M(M-1)d\leq {\frac {1}{2}}nM^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51149bf39b54b55836578a384cb5c057fd22bbcc)
which given that
is equivalent to
![{\displaystyle M\leq {\frac {2d}{2d-n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d1d9b873fd325a85df5002d13bd3d80a6f91b97)
Since
is even, it follows that
![{\displaystyle M\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1961cd67222bf634ad2a5181743dcef8bce9f6fc)
This completes the proof of the bound.
See also[edit]
References[edit]